package tx_0425_5;

import java.util.*;
/**
 * -----------------------------------------------------------------------------------------------------
 * 现在有一个长度为n的价格数组a，表示某只股票每天的价格，你每天做多买入或卖出该只股票的1手股票，买入或者卖出没有手续费，
 * 且卖出股票前必须手里已经有股票才能卖出，但是持有的股票数目不受限制，并且初始资金为m元。你再任意时刻都不能进行透支，
 * 所以你的资金必须始终大于等于0，请问你在n天结束之后，拥有的最大总资产是多少？（总资产：股票数目*股票价格+现金）
 * -----------------------------------------------------------------------------------------------------
 * 输入描述：第一行两个整数n,m(1<=n<=2000,1<=m)
 *         第二行n个正整数a(n)(1<=a[n])，其中a(i)表示股票在第i天的售价
 * 输出描述：输出n天结束后，拥有的最大总资产
 * 示例：
 *      输入 6 2
 *          2 3 1 1 1 2
 *      输出 6
 *
 *      输入 3 2
 *          1 1 4
 *      输出 8
 *------------------------------------------------------------------------------------------------------
 * 解题思路：
 *      动态规划
 *      问题：第n天拥有的最大资产
 *      状态：F(i,j)：第i天拥有j手股票的最大资产，值得注意的是，资产表示为资金+股票数*最后一天股票价格
 *      状态转移方程：
 *                  F(i-1,j-1) --> F(i,j)
 *                  昨天买入：判断有没有资金买  资金=昨天的资产-昨天的股票数*最后一天的价格=F(i-1,j-1)-(j-1)*a[n-1]
 *                                         当天股票价格=a[i]  两者相减就行
 *                          买入后的资产=昨天的资产-昨天的股票价格+股票在最后一天的价格=a[n-1]-a[i] +ret[i-1][j-1]
 *                          如果没有资金买，就不考虑这种情况,就让它为-1
 *                          值得注意的是，在买入之后，股票数量一定大于零，所以要加一个j>0的判断条件
 *                  F(i-1,j+1) --> F(i,j)
 *                  昨天卖出：判断有没有股票卖  股票数>0即j>0  并且  F(i-1，j+1)存在  即不为-1
 *                          如果不能卖，就不考虑这种情况，就让它为-1
 *                  F(i-1,j)  --> F(i,j)
 *                  不操作：资产等于前一天
 *       初始状态：F(0,0)  F(0,1)  即第一天没买，第一天买了两种情况
 *               因为转移方程里面有i-1，所以要考虑i=0
 *               初始状态就是第一天的状态，F(0,0)表示没买，那资产等于初始资金m
 *               第一天钱购买那F(0,1)等于m-a[0]+a[n-1]，钱不够买那就不存在这种情况，让它等于-1
 *       返回结果：我们要知道最后一天的最大资产，那就要在最后一天的所有情况中找对大值即在F(n-1)中找最大的
 * -----------------------------------------------------------------------------------------------------
 */
public class TestDemo {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //输入n为天数
        int n = sc.nextInt();
        //输入m为初始资金
        int m = sc.nextInt();
        //输入数组a为每一天的股票价格
        int[] a = new int[n];
        for(int i=0;i<n;++i){
            a[i]=sc.nextInt();
        }
        //定义状态数组
        int[][] ret = new int[n][n+1];
        //设置初始状态
        if(m>=a[0])
            ret[0][1] = m-a[0]+a[n-1];
        else
            ret[0][1] = -1;
        ret[0][0] = m;
        //状态转移
        for(int i =1;i<n;i++){
            //因为股票数不可能大于天数，所以j<=i+1,并且不能大于总股票数，所以j<n
            for(int j = 0;j<=i+1 && j<n;j++){
                //能不能卖
                int a1;
                if(ret[i-1][j+1]!=-1)
                    a1 = a[i]-a[n-1] +ret[i-1][j+1];
                else
                    a1 = -1;
                //能不能买
                int b1;
                if(j>0 && ret[i-1][j-1]-(j-1)*a[n-1] >= a[i])
                    b1 = a[n-1]-a[i] +ret[i-1][j-1];
                else
                    b1 = -1;
                //不买不卖
                int c1 = ret[i-1][j];
                ret[i][j] = Math.max(a1,Math.max(b1,c1));
            }
        }
        //返回结果
        int max = 0;
        for(int j=0;j<n;++j){
            max=Math.max(ret[n-1][j],max);
        }
        System.out.println(max);
    }
}
